package cn.edu.jxau.test;

import java.util.Arrays;

/**
 * quick find实现
 * @author 付大石
 */
public class UnionFind {

    /**
     * 触点集
     */
    private int[] idArr;

    /**
     * 连通分量个数
     */
    private int count;

    public UnionFind(int count) {

        this.count = count;
        idArr = new int[count];
        for (int i = 0; i < idArr.length; i++) {
            idArr[i] = i;
        }
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int find(int p) {
        return idArr[p];
    }

    public int count() {
        return count;
    }

    public void union(int p, int q) {

        int pId = find(p);
        int qId = find(q);
        if (pId == qId) {
            return;
        }

        // 连接两个连通分量 //
        for (int i = 0; i < idArr.length; i++) {
            if (idArr[i] == pId) {
                idArr[i] = qId;
            }
        }
        count--; // 两个连通分量连接成一个，连通分量数减一
    }
    
    @Override
    public String toString() {
        
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("count:").append(count).append("\t");
        stringBuilder.append(Arrays.toString(idArr));
        return stringBuilder.toString();
    }
}
